package implementation.sort;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;


public class HeapSort extends AbstractSorter {

    public HeapSort() {
        super(SorterType.HEAP);
    }

    public <T> void sort(Comparator<T> comparator, List<T> list) {
        sort(comparator, list, 0, list.size() - 1);
    }

    /*   protected <T> void sort(Comparator<T> tComparator, List<T> ts, int start, int end) {
        for (int k = (end - 1) / 2; k >= start; k--) {
            sink(tComparator, ts, k, end);
        }
        while (end > start) {
            swap(ts, start, end--);
            sink(tComparator, ts, start, end);
        }
    }

    private <T> void sink(Comparator<T> tComparator, List<T> ts, int i, int n) {
        while ((((i + 1) * 2) - 1) <= n) {
            int j = ((i + 1) * 2) - 1;
            if (j < n && !greater(tComparator, ts, j, j + 1)) {
                j++;
            }
            if (greater(tComparator, ts, i, j)) break;
            swap(ts, i, j);
            i = j;
        }
    }*/


    protected <T> void sort(Comparator<T> tComparator, List<T> ts, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            add(tComparator, ts, i, end);
        }
        for (int j = end; j > 0; j--) {
            swap(ts, start, j);
            sink(tComparator, ts, j, end);
        }

    }

    private <T> void sink(Comparator<T> tComparator, List<T> ts, int j, int end) {
        while ((2 * j + 1) <= end) {
            if ((2 * j + 2 > end) || greater(tComparator, ts, 2 * j + 1, 2 * j + 2)) {
                if (greater(tComparator, ts, 2 * j + 1, j)) {
                    swap(ts, 2 * j + 1, j);
                    j = 2 * j + 1;
                }
            } else {
                if (greater(tComparator, ts, 2 * j + 2, j)) {
                    swap(ts, 2 * j + 2, j);
                    j = 2 * j + 2;
                }
            }
        }
    }

    private <T> void add(Comparator<T> tComparator, List<T> ts, int i, int end) {
        while (i > 0 && greater(tComparator, ts, i, (i - 1) / 2)) {
            swap(ts, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }

    }


}
